#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, q, fa[500005], b, lans[500005];

int get_fa(int i) {
	if (fa[i] == i) return fa[i];
	return fa[i] = get_fa(fa[i]);
}


namespace CR200Jplus {
	int isp[500005], tot, col[500005];
	void insert(int x) {
		//cout << "insert " << fa[x] << " is " << col[fa[x]] << "\n";
		tot += (col[fa[x]] == 0);
		++col[fa[x]];

	}
	void erase(int x) {
		tot -= (col[fa[x]] == 1);
		--col[fa[x]];
	}
	void main() {
		for (int _ = 1; _ <= q; ++_) {
			int L, R, ans = 1ll << 60;
			cin >> L >> R;
			int anst = 0;
			for (int i = L; i <= R; ++i) {
				anst += (!isp[fa[i]]);
				isp[fa[i]] = 1;
			}
			int r = L - 1;
			for (int l = L; l <= R; ++l) {
				while (r <= R && tot != anst) {
					++r;
					if (r <= R) insert(r);
				}
				if (r <= R) {
					ans = min(ans, r - l + 1);
				}
				erase(l);
			}
			cout << ans << "\n";
			for (int i = L; i <= R; ++i) isp[fa[i]] = 0;
			for (int i = L; i <= R; ++i) col[fa[i]] = 0;
			tot = 0;
		}
	}
}

namespace CRH380D {
	int st[21][500005];
	int query(int l, int r) {
		int x = __lg(r - l + 1);
		return st[x][l] | st[x][r - (1 << x) + 1];
	}
	inline int chk(int L, int R, int l, int r) {
		return query(L, R) == query(l, r);
	}
	vector<int> pos[500005];
	inline int pre(int x, int i) {
		int it = upper_bound(pos[x].begin(), pos[x].end(), i) - pos[x].begin() - 1;
		if (it >= 0 && it < pos[x].size()) return pos[x][it];
		return 0;
	}
	inline int suf(int x, int i) {
		int it = lower_bound(pos[x].begin(), pos[x].end(), i) - pos[x].begin();
		if (it >= 0 && it < pos[x].size()) return pos[x][it];
		return n + 1;
	}
	void main() {
		for (int i = 1; i <= n; ++i) {
			st[0][i] = (1 << (fa[i] - 1));
		}
		for (int j = 1; j <= 20; ++j) {
			for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
				st[j][i] = st[j - 1][i] | st[j - 1][i + (1 << (j - 1))];
			}
		}
		for (int i = 1; i <= n; ++i) {
			pos[fa[i]].push_back(i);
		}
		while (q--) {
			int L, R, ans = 1ll << 60;
			cin >> L >> R;
			vector<int> dt1;
			for (int j = 1; j <= b; ++j) {
				for (int dt = -1; dt <= 1; ++dt) {
					dt1.push_back(pre(j, R) + dt);
					dt1.push_back(pre(j, pre(j, R) - 1) + dt);
					dt1.push_back(suf(j, L) + dt);
					dt1.push_back(suf(j, suf(j, L) + 1) + dt);
				}
			}
			for (auto i : dt1) {
				for (auto j : dt1) {
					if (i < L || j > R || i > j) continue;
					if (chk(L, R, i, j)) ans = min(ans, j - i + 1);
				}
			}
			cout << ans << "\n";
		}
	}
}

signed main() {
	freopen("destory.in", "r", stdin); freopen("destory.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= n; ++i) {
		fa[i] = i;
	}
	while (m--) {
		int u, v;
		cin >> u >> v;
		u = get_fa(u); v = get_fa(v);
		if (u != v) {
			fa[u] = v;
		}
	}
	for (int i = 1; i <= n; ++i) {
		get_fa(i);
	}
	map<int, int> col;
	for (int i = 1; i <= n; ++i) {
		if (col.count(fa[i])) fa[i] = col[fa[i]];
		else {
			int t = col.size() + 1;
			col[fa[i]] = t;
			fa[i] = col[fa[i]];
		}
	}
	b = col.size();
	if (n * q <= 1e8) {
		CR200Jplus::main();
	} else if (b <= 5) CRH380D::main();
	return 0;
}
